package pl.dsp.dsp1.processing;

public class FFTFactory {

	private Signal signal;

	public FFTFactory(Signal signal) {
		this.signal = new Signal(signal);
		int targetSize = (int) Math.pow(2,
				(int) (Math.log(signal.size()) / Math.log(2)));
		while (this.signal.size() > targetSize) {
			this.signal.remove(this.signal.size() - 1);
		}
	}

	public Signal getFFT() {
		Signal resultSignal = new Signal(signal.getT1(),
				signal.getSamplingPeriod());
		int[] sampleOrder = getReorderedSamples();
		for (int i = 0; i < signal.size(); i++) {
			resultSignal.add(signal.get(sampleOrder[i]));
		}

		int stepSize = 2;
		for (int step = 0; step < getBitLength(); step++) {
			for (int block = 0; block < signal.size() / stepSize; block++) {
				runPartialFFT(resultSignal, stepSize, block * stepSize);
			}
			stepSize <<= 1;
		}

		for (int i = 0; i < signal.size(); i++) {
			resultSignal.set(
					i,
					resultSignal.get(i).divide(
							new ComplexValue(signal.size(), 0)));
		}
		return resultSignal;
	}

	private void runPartialFFT(Signal workingSignal, int stepSize,
			int startingIndex) {
		for (int i = startingIndex; i < startingIndex + stepSize / 2; i++) {
			int j = i + stepSize / 2;

			double exp = -2 * Math.PI * (i - startingIndex) / (double) stepSize;
			SignalValue upper = workingSignal.get(i);
			SignalValue lower = ComplexValue.euler(exp).multiply(
					workingSignal.get(j));
			workingSignal.set(i, lower.add(upper));
			workingSignal.set(j,
					lower.multiply(new ComplexValue(-1, 0)).add(upper));
		}
	}
	
	public Signal getIFFT() {
		Signal workingSignal = new Signal(signal.getT1(),
				signal.getSamplingPeriod());
		int[] sampleOrder = getReorderedSamples();
		for (int i = 0; i < signal.size(); i++) {
			workingSignal.add(signal.get(sampleOrder[i]));
		}

		int stepSize = 2;
		for (int step = 0; step < getBitLength(); step++) {
			for (int block = 0; block < signal.size() / stepSize; block++) {
				runPartialIFFT(workingSignal, stepSize, block * stepSize);
			}
			stepSize <<= 1;
		}

		return workingSignal;
	}

	private void runPartialIFFT(Signal workingSignal, int stepSize,
			int startingIndex) {
		for (int i = startingIndex; i < startingIndex + stepSize / 2; i++) {
			int j = i + stepSize / 2;

			double exp = 2 * Math.PI * (i - startingIndex) / (double) stepSize;
			SignalValue upper = workingSignal.get(i);
			SignalValue lower = ComplexValue.euler(exp).multiply(
					workingSignal.get(j));
			workingSignal.set(i, lower.add(upper));
			workingSignal.set(j,
					lower.multiply(new ComplexValue(-1, 0)).add(upper));
		}
	}

	private int getBitLength() {
		int length = signal.size() - 1;
		int bitLength = 0;

		while (length > 0) {
			length >>= 1;
			bitLength++;
		}

		return bitLength;
	}

	private int[] getReorderedSamples() {
		int[] result = new int[signal.size()];
		for (int i = 0; i < result.length; i++) {
			result[i] = reverseBits(i);
		}

		return result;
	}

	private int reverseBits(int number) {
		int bitLength = getBitLength();
		int result = 0;

		for (int i = 0; i < bitLength; i++) {
			result <<= 1;
			result |= (number & 1);
			number >>= 1;
		}

		return result;
	}
}
